package com.clstu.recursion;

/**
 * 探究8皇后问题,8*8的格子放8个皇后,每两个皇后不能在 同一行同一列或者同一斜线(45°或135°的斜线)
 */
public class Queue8 {
    //首先思路,用一维数组代替二维数组就行,因为8个皇后不可能在同一行,所以索引表示行号就行了,val表示在这行的第几列
    private static int max = 8;//皇后个数
    private static int[] queues = new int[8];//存放8个皇后的位置信息
    private static int count = 0;
    public static void main(String[] args) {
        //测试能否找到
        check(0);
        System.out.println("种共有解法:"+count+"种");
    }

    //(递归回溯)
    //编写方法放置第n个皇后,n既表示皇后的个数,也表示在棋盘上的行数
    public static void check(int n){
        //如果找到了一种方案,直接return
        if(n==8){//因为for循环的最大为7,如果n+1=8则表明已经皇后都摆放好了
            count++;//计算有多少种解法
            printQueue(queues);
            return;
        }
        //依次在当前行的每一列放入皇后,判断是否冲突
        for (int i = 0; i < max; i++) {
            //放入皇后再试探是否冲突
            queues[n] = i;
            //如果冲突,回溯,试探下一列的位置是否ok
            if(judge(queues,n)){
                //试探下一列直接进入下一次循环就可以了,而不是break,更不是return,需要注意!!!
                continue;
            }
            //如果不冲突,就再下一行的每一列反复试探,试探完了仍然会进入到下一列,因为要遍历找每一个种解法
            check(n+1);
        }
    }

    //编写方法判断第n个皇后是否跟前面的皇后产生了冲突
    public static boolean judge(int[] queues,int n){
        for (int i = 0; i < n; i++) {
            //如果在同一列,或者在同意斜线
            if(queues[n]==queues[i] || Math.abs(queues[n]-queues[i])==n-i){
                return true;
            }
        }
        //如果都没有冲突,说明不冲突
        return false;
    }

    //编写方法打印所有的皇后的位置
    public static void printQueue(int[] queues){
        for (int queue : queues) {
            System.out.print(queue+"  ");
        }
        System.out.println();
    }
}
